//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 19 
// 
// Related Topics 树 二叉搜索树 数学 动态规划 二叉树 
// 👍 1543 👎 0

package com.cute.leetcode.editor.cn;
public class UniqueBinarySearchTrees {
    public static void main(String[] args) {
        Solution solution = new UniqueBinarySearchTrees().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 并没有什么思路，看的代码随想录的题解
         * dp[i]表示的是有i个节点的树的数量
         * 最大值为i的时候
         * 头结点为j时树的种类 = 左子树有j-1个节点*右子树有i-j个节点
         * 比如i = 7, j = 3 此时比j小的数只有1 2, 比j大的数有4 5 6 7
         * 所以以3为根节点时的树的数量为dp[2]*dp[4],只需要树的数量，不关心具体结构
         * 对于所有j来说，dp[i] += dp[j-1]*dp[i-j] , j = 1...i
         * 初始化dp[0] = 1,可以认为空树也算是一种情况
         * 可以手动模拟一下n=3的情况的推导过程
         */
        public int numTrees(int n) {
            int[] dp = new int[n+1];
            dp[0] = 1;
            for (int i = 1; i<=n; i++){
                for (int j = 1; j<=i; j++){
                    // i表示当前共有多少节点，j代表的是根节点的值
                    // j - 1为左子树节点数，i-j是右子树节点数
                    dp[i] += dp[j-1]*dp[i-j];
                }
            }
            return dp[n];
        }

        /**
         * 三刷我还是没思路，只能看题解
         * 构建树的种类与节点值无关，只与节点数量有关！！！
         * 所以假设节点共有i个
         *  此时左子树可以分配0个，右子树分配i-1个
         *  左子树分配1个，右子树分配i-2个...
         *  左子树分配i-1个，右子树分配0个
         */
    }
//leetcode submit region end(Prohibit modification and deletion)

}